/**
 * 
 */
package edu.umd.clip.lm.model.training;

import edu.umd.clip.lm.model.*;
import edu.umd.clip.lm.questions.*;
import edu.umd.clip.lm.factors.*;
import edu.umd.clip.lm.util.tree.*;
import edu.umd.clip.lm.util.*;

import java.util.*;
/**
 * @author Denis Filimonov <den@cs.umd.edu>
 *
 */
public class QuestionGenerator {
	private List<Question> questions;

	public void initialize(final LanguageModel lm) {
		initialize(lm, true);
	}

	public void initialize(final LanguageModel lm, boolean useIdentityQuestions) {
		questions = new ArrayList<Question>(1000);
		FactorTupleDescription desc = Experiment.getInstance().getTupleDescription();
		byte order = lm.getOrder();

		// generate questions about overt factors
		if (useIdentityQuestions) {
			for(byte idx : desc.getOvertFactors()) {
				if (idx == desc.getMainFactorIndex()) continue;
				edu.umd.clip.lm.factors.Dictionary dict = desc.getDictionary(idx);
				DictionaryIterator it = dict.iterator(true);
				while(it.hasNext()) {
					int value = it.next();
					for(byte time=-1; time > -order; --time) {
						Question q = new IdentityQuestion(time, idx, value);
						questions.add(q);
					}
				}

			}
		}
		// generate question about prefixes in the word tree
		/*
		{
			final byte factorIdx = desc.getFactorIndex(forest.getWordTree().getWordFactor());
			BinaryTreeFinder<WordTreePayload> finder = new BinaryTreeFinder<WordTreePayload>() {
				public boolean apply(BinaryTree<WordTreePayload> node) {
					if (node.getParent() != null) {
						BinaryPrefix prefix = node.getPayload().prefix;
						if (prefix.getSize() <= 18) {
							for(byte time = -1; time > -forest.getOvertOrder(); --time) {
								BinaryPrefixQuestion q = new BinaryPrefixQuestion(time, factorIdx, false, prefix);
								questions.add(q);
							}
						}
					}
					return false;
				}
			};
			forest.getWordTree().getTree().searchPreorder(finder);
		}
		*/
		// generate questions about HFT prefixes
		{
			BinaryTreeFinder<HFTPayload> finder = new BinaryTreeFinder<HFTPayload>() {
				public boolean apply(BinaryTree<HFTPayload> node) {
					if (node.getParent() != null) {
						BinaryPrefix prefix = node.getPayload().prefix;
						for(byte time=-1; time > -lm.getHiddenOrder(); --time) {
							Question q = new BinaryPrefixQuestion(time, true, prefix);
							questions.add(q);
						}
					}
					return false;
				}
			};
			lm.getHFT().getTree().searchPreorder(finder);
		}
	}

	public ListIterator<Question> iterator(Iterable<Question> trueQuestions, Iterable<Question> falseQuestions) {
		return new QuestionIterator(trueQuestions, falseQuestions);
	}
	
	public Iterator<Question> complexIterator(Question q, SimpleList<Question> trueQuestions, SimpleList<Question> falseQuestions) {
		return new ComplexQuestionIterator(q, trueQuestions, falseQuestions);
	}
	
	private class QuestionIterator implements ListIterator<Question> {
		private ListIterator<Question> iterator;
		private SimpleList<Question> outstandingQuestions = new SimpleList<Question>();
		private Iterable<Question> trueQuestions;
		private Iterable<Question> falseQuestions;
		//private static final int maxDistance = 5;
		
		protected QuestionIterator(Iterable<Question> trueQuestions, Iterable<Question> falseQuestions) {
			iterator = questions.listIterator();
			this.trueQuestions = trueQuestions;
			this.falseQuestions = falseQuestions;
		}
		
		public boolean hasNext() {
			while(outstandingQuestions.isEmpty() && iterator.hasNext()) {
				Question q = iterator.next();
				if (isGoodQuestion(q)) {
					outstandingQuestions = outstandingQuestions.add(q);
					break;
				}
			}
			return !outstandingQuestions.isEmpty();
		}
		
		/* (non-Javadoc)
		 * @see java.util.Iterator#next()
		 */
		public Question next() {
			hasNext();
			Question q = outstandingQuestions.head();
			outstandingQuestions = outstandingQuestions.tail();
			return q;
		}

		/* (non-Javadoc)
		 * @see java.util.Iterator#remove()
		 */
		public void remove() {
			throw new Error("not implemented");
		}

		protected boolean isGoodQuestion(Question question) {
			return !isImplied(question, trueQuestions, falseQuestions);
			/*
			boolean testedPrefixLength = false;
			if (!question.isAboutHidden() && question.getQuestionType() == Question.BINARY_PREFIX_QUESTION) {
				for(Question q : trueQuestions) {
					if (!q.isAboutHidden() && 
							q.getTimeOffset() == question.getTimeOffset() && 
							q.getQuestionType() == Question.BINARY_PREFIX_QUESTION) 
					{
						testedPrefixLength = true;
						
						// the first question is the most precise one
						BinaryPrefix askedPrefix = ((BinaryPrefixQuestion) q).getPrefix();
						BinaryPrefix newPrefix = ((BinaryPrefixQuestion) question).getPrefix();
						if (!askedPrefix.isPrefixOf(newPrefix) || newPrefix.getSize() > askedPrefix.getSize() + maxDistance) {
							return false;
						}
						break;
					}
				}
				
				if (!testedPrefixLength) {
					if (((BinaryPrefixQuestion) question).getPrefix().getSize() > maxDistance) return false;
				}
			}
			
			for(Question q : trueQuestions) {
				if (question.implication(q, true) != null) return false; 
			}
			
			for(Question q : falseQuestions) {
				if (question.implication(q, false) != null) return false;
			}
			return true;
			*/
		}

		public void add(Question q) {
			// NOTE: this violates the semantics of ListIterator.add which is supposed to insert the element before the cursor
			outstandingQuestions = outstandingQuestions.add(q);
		}

		public boolean hasPrevious() {
			throw new UnsupportedOperationException();
		}

		public int nextIndex() {
			throw new UnsupportedOperationException();
		}

		public Question previous() {
			throw new UnsupportedOperationException();
		}

		public int previousIndex() {
			throw new UnsupportedOperationException();
		}

		public void set(Question arg0) {
			throw new UnsupportedOperationException();
		}
	}
	
	public static boolean isImplied(Question question, Iterable<Question> trueQuestions, Iterable<Question> falseQuestions) {
		for(Question q : trueQuestions) {
			if (question.implication(q, true) != null) return true; 
		}
		
		for(Question q : falseQuestions) {
			if (question.implication(q, false) != null) return true;
		}
		return false;
	}
	
	public class ComplexQuestionIterator implements Iterator<Question> {
		private Question question;
		private Question notQuestion;
		private final static int AND_STAGE = 1;
		private final static int AND_NOT_STAGE = 2;
		private final static int NOT_AND_STAGE = 3;
		private final static int NOT_AND_NOT_STAGE = 4;
		
		private int stage;
		private QuestionIterator iterator;
		private SimpleList<Question> trueQuestions;
		private SimpleList<Question> falseQuestions;
		private ComplexQuestionIterator(Question question, SimpleList<Question> trueQuestions, SimpleList<Question> falseQuestions) {
			this.question = question;
			this.notQuestion = new NotQuestion(question);
			this.trueQuestions = trueQuestions;
			this.falseQuestions = falseQuestions;
			setStage(AND_STAGE);
		}
		
		private class QuestionIteratorPrvt extends QuestionIterator {
			/**
			 * @param trueQuestions
			 * @param falseQuestions
			 */
			public QuestionIteratorPrvt(SimpleList<Question> trueQuestions,
					SimpleList<Question> falseQuestions) {
				super(trueQuestions, falseQuestions);
			}

			/* (non-Javadoc)
			 * @see edu.umd.clip.lm.model.training.QuestionGenerator.QuestionIterator#isGoodQuestion(edu.umd.clip.lm.questions.Question)
			 */
			@Override
			protected boolean isGoodQuestion(Question q) {
				return !(question.isAboutHidden() && q.isAboutHidden()) && super.isGoodQuestion(q);
			}
		}
		
		private void setStage(int stage) {
			this.stage = stage;
			switch(stage) {
			case AND_STAGE:
				iterator = new QuestionIteratorPrvt(trueQuestions.add(question), falseQuestions);
				break;
			case AND_NOT_STAGE:
				iterator = new QuestionIteratorPrvt(trueQuestions.add(question), falseQuestions);
				break;
			case NOT_AND_STAGE:
				iterator = new QuestionIteratorPrvt(trueQuestions, falseQuestions.add(question));
				break;
			case NOT_AND_NOT_STAGE:
				iterator = new QuestionIteratorPrvt(trueQuestions, falseQuestions.add(question));
				break;
			default:
				iterator = null;
			}
		}

		/* (non-Javadoc)
		 * @see java.util.Iterator#hasNext()
		 */
		public boolean hasNext() {
			if (iterator == null) return false;
			if (iterator.hasNext()) return true;
			setStage(stage+1);
			if (iterator == null) return false;
			return iterator.hasNext();
		}

		/* (non-Javadoc)
		 * @see java.util.Iterator#next()
		 */
		public Question next() {
			Question q = iterator.next();
			switch(stage) {
			case AND_STAGE:
				return new AndQuestion(question, q);
			case AND_NOT_STAGE:
				return new AndQuestion(question, new NotQuestion(q));
			case NOT_AND_STAGE:
				return new AndQuestion(notQuestion, q);
			case NOT_AND_NOT_STAGE: 
				return new AndQuestion(notQuestion, new NotQuestion(q));
			}
			return null;
		}

		/* (non-Javadoc)
		 * @see java.util.Iterator#remove()
		 */
		public void remove() {
			throw new Error("not implemented");
		}
		
	}

	public List<Question> getQuestions() {
		return questions;
	}
}
